//给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。 
//
// 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求
//： 
//
// 
// 路径途经的所有单元格都的值都是 0 。 
// 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。 
// 
//
// 畅通路径的长度 是该路径途经的单元格总数。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [[0,1],[1,0]]
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
//输出：4
// 
//
// 示例 3： 
//
// 
//输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length 
// n == grid[i].length 
// 1 <= n <= 100 
// grid[i][j] 为 0 或 1 
// 
// Related Topics 广度优先搜索 数组 矩阵 
// 👍 139 👎 0

package com.cute.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class ShortestPathInBinaryMatrix {
    public static void main(String[] args) {
        Solution solution = new ShortestPathInBinaryMatrix().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * BFS遍历，这里使用BFS效率会高，因为求的是最短路径，使用BFS时只要到达了终点就是最先到达的
         * BFS一开始便尝试了所有情况，所以先到达的路径就是最短的
         * 左上角和右下角都必须是0，这是前提条件
         * 使用一个数组来保存八个方向
         * 遍历时对八个方向中不越界的下标位置进行更新
         * 本题解直接使用了原始数组grid来存储了路径距离
         * 所以遍历的时候如果grid不为0就说明已经访问过了
         * 如果下一个位置没有越界且没被访问过，那么其位置的值设置为当前路径+1
         * 最后判断grid[n-1][n-1]是否为0，如果仍然为0说明访问不到，返回-1，否则返回其值即可
         */

        //八个方向的增量
        private final int[][] directions  =  {{0,1},{0,-1},{-1,0},{1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
        private int row;
        private int col;
        public int shortestPathBinaryMatrix(int[][] grid) {
            row = grid.length;
            col = grid.length;
            //不满足题意的直接返回
            if (grid[0][0]!=0 || grid[row-1][col-1]!=0) return -1;
            //使用队列储存各个可以访问的坐标
            Queue<int[]> pos = new LinkedList<>();
            //能运行到这个位置说明距离至少为1，将起始位置的值直接赋1即可
            grid[0][0] = 1;
            pos.add(new int[]{0,0});//并想队列中添加坐标对
            int preLen;
            while (!pos.isEmpty()&&grid[row-1][col-1]==0){
                int[] xy = pos.poll();//拿到坐标对
                preLen = grid[xy[0]][xy[1]];//根据坐标获取当前的路径长度
                for (int i = 0; i < 8 ; i++) {
                    //遍历8个方向的所有情况
                    int newX = xy[0] + directions[i][0];
                    int newY = xy[1] + directions[i][1];
                    if (inGrid(newX, newY) && grid[newX][newY]==0){
                        //只有没有越界且没有访问过才可以进入此循环，更新距离并加入队列
                        grid[newX][newY] = preLen+1;
                        pos.add(new int[]{newX,newY});
                    }
                }
            }
            //如果末尾仍然为0则说明访问不到，否则返回结果即可
            return grid[row-1][col-1] == 0 ? -1: grid[row-1][col-1];
        }

        public boolean inGrid(int x, int y){
            return x >= 0 && x < row && y >=0 && y <col;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}